package com.ww.springboot.boot.algorithm.leetcode1;

/**
 * 描述：
 *
 * @author 🧑 ‍wanwei
 * @since 2022-03-23 09:23
 */
public class AY440字典序第K小数字2 {

    public static void main(String[] args) {


        //System.out.println(findKthNumber(957747794, 424238336));

        System.out.println(getSteps(43, 957747794));
    }


    /**
     * 1.先写一个方法 计算i节点 在n字典树中的子节点数
     * 2.计算子节点数与K的剩余差值,如果小于K 则往右移动节点 如果大于k 则往下移动节点
     * i 的下一层节点是i*10 ~i*10+9
     * 下下一层的总节点数是 i*10*10  (i*10+9)*10+9
     *
     *
     *
     * @param n
     * @param k
     * @return
     */
    public static int findKthNumber(int n, int k) {
        int curr = 1;
        while (k > 0) {
            int total = getSteps(curr, n);
            //如果k>total节点数 则说明在下一个节点
            if (k > total) {
                k -= total;
                curr++;
            } else if (k == 1) {
                // 则直接去取curr
                break;
            } else {
                //否则k在此节点下 则往下继续筛选
                k--;
                curr *= 10;
            }
        }
        //此时的curr 已经找到
        return curr;
    }


    /**
     * 计算curr 节点下面的所有子节点数
     *
     * @param curr
     * @param n
     * @return
     */
    public static int getSteps(int curr, int n) {
        int steps = 0;
        int first = curr;
        int last = curr;
        while (first <= n) {
            steps += Math.min(last, n) - first + 1;
            if (first > Integer.MAX_VALUE / 10 + 1) {
                break;
            }
            first = first * 10;
            last = last * 10 + 9;
        }
        return steps;
    }

}
